Thực đơn
Mã Hamming Ví dụ dùng (11,7) mã HammingLấy ví dụ chúng ta có một từ dữ liệu dài 7 bit với giá trị là "0110101". Để chứng minh phương pháp các mã Hamming được tính toán và được sử dụng để kiểm tra lỗi, xin xem bảng liệt kê dưới đây. Chữ d (data) được dùng để biểu thị các bit dữ liệu và chữ p (parity) để biểu thị các bit chẵn lẻ (parity bits).
Đầu tiên, các bit của dữ liệu được đặt vào vị trí tương thích của chúng, sau đó các bit chẵn lẻ cho mỗi trường hợp được tính toán dùng quy luật bit chẵn lẻ số chẵn[1].
Thứ tự bit | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|
Vị trí bit chẵn lẻ và các bit dữ liệu | p1 | p2 | d1 | p4 | d2 | d3 | d4 | p8 | d5 | d6 | d7 |
Nhóm dữ liệu (không có bit chẵn lẻ): | 0 | 1 | 1 | 0 | 1 | 0 | 1 | ||||
p1 | 1 | 0 | 1 | 0 | 1 | 1 | |||||
p2 | 0 | 0 | 1 | 0 | 0 | 1 | |||||
p4 | 0 | 1 | 1 | 0 | |||||||
p8 | 0 | 1 | 0 | 1 | |||||||
Nhóm dữ liệu (với bit chẵn lẻ): | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
Nhóm dữ liệu mới (new data word) - bao gồm các bit chẵn lẻ - bây giờ là "10001100101". Nếu chúng ta thử cho rằng bit cuối cùng bị thoái hóa (gets corrupted) và bị lộn ngược từ 1 sang 0. Nhóm dữ liệu mới sẽ là "10001100100"; Dưới đây, chúng ta sẽ phân tích quy luật kiến tạo mã Hamming bằng cách cho bit chẵn lẻ giá trị 1 khi kết quả kiểm tra dùng quy luật số chẵn bị sai.
Thứ tự bit | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | ||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Vị trí bit chẵn lẻ và các bit dữ liệu | p1 | p2 | d1 | p3 | d2 | d3 | d4 | p4 | d5 | d6 | d7 | Kiểm chẵn lẻ | Bit chẵn lẻ |
Nhóm dữ liệu nhận được: | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | |
p1 | 1 | 0 | 1 | 0 | 1 | 0 | Sai | 1 | |||||
p2 | 0 | 0 | 1 | 0 | 0 | 0 | Sai | 1 | |||||
p4 | 0 | 1 | 1 | 0 | Đúng | 0 | |||||||
p8 | 0 | 1 | 0 | 0 | Sai | 1 |
Bước cuối cùng là định giá trị của các bit chẵn lẻ (nên nhớ bit nằm dưới cùng được viết về bên phải - viết ngược lại từ dưới lên trên). Giá trị số nguyên của các bit chẵn lẻ là 11(10), và như vậy có nghĩa là bit thứ 11 trong nhóm dữ liệu (data word) - bao gồm cả các bit chẵn lẻ - là bit có giá trị không đúng, và bit này cần phải đổi ngược lại.
p8 | p4 | p2 | p1 | ||
---|---|---|---|---|---|
Nhị phân | 1 | 0 | 1 | 1 | |
Thập phân | 8 | 2 | 1 | Σ = 11 |
Việc đổi ngược giá trị của bit thứ 11 làm cho nhóm
10001100100trở lại thành
10001100101.Bằng việc bỏ đi phần mã Hamming, chúng ta lấy được phần dữ liệu gốc với giá trị là
0110101.Lưu ý, các bit chẵn lẻ không kiểm tra được lẫn nhau, nếu chỉ một bit chẵn lẻ bị sai thôi, trong khi tất cả các bit khác là đúng, thì chỉ có bit chẵn lẻ nói đến là sai mà thôi và không phải là các bit nó kiểm tra (not any bit it checks).
Cuối cùng, giả sử có hai bit biến đổi, tại vị trí x và y. Nếu x và y có cùng một bit tại vị trí 2k trong đại diện nhị phân của chúng, thì bit chẵn lẻ tương ứng với vị trí đấy kiểm tra cả hai bit, và do đó sẽ giữ nguyên giá trị, không thay đổi. Song một số bit chẵn lẻ nào đấy nhất định phải bị thay đổi, vì x ≠ y, và do đó hai bit tương ứng nào đó có giá trị x và y khác nhau. Do vậy, mã Hamming phát hiện tất cả các lỗi do hai bit bị thay đổi — song nó không phân biệt được chúng với các lỗi do 1 bit bị thay đổi.
Thực đơn
Mã Hamming Ví dụ dùng (11,7) mã HammingLiên quan
Mã Mã di truyền Mã Siêu Mã số điện thoại quốc tế Mãn Châu Quốc Mã Morse Mã Gia Kỳ Mã vạch Mãn Châu Mã hóa video hiệu quả caoTài liệu tham khảo
WikiPedia: Mã Hamming http://www.ee.unb.ca/cgi-bin/tervo/hamming.pl http://www.apple.lu/stlau/hamming.php http://pdc.ro.nu/hamming.html http://en.wikipedia.org/wiki/Galois_field http://en.wikipedia.org/wiki/Modulo